package leetcode_200;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;

/**
 *@author 周杨
 *WordBreakII_140 类似139题 用dp方法 要返回所有合适结果
 *describe:map保存会超时 直接用dfs递归搜索 AC 99%
 *2018年6月4日 下午2:14:54
 */
public class WordBreakII_140 {
	List<String> res;
	private int min = Integer.MAX_VALUE;;
    private int max = 0;
	public static void main(String[] args) {
		WordBreakII_140 test=new WordBreakII_140();
		List<String> list=new ArrayList<String>();
		list.add("cat");
		list.add("cats");
		list.add("and");
		list.add("sand");
		list.add("dog");
		test.wordBreak("catsanddog",list);

	}
	
	/**
	 * describe:借鉴之前的思想 用map保存相应数组 但是超时
	 * 2018年6月4日 下午1:42:47
	 */
	public List<String> wordBreak(String s, List<String> wordDict) {
        res=new ArrayList<String>();
        Map<Integer,List<StringBuilder>> map=new HashMap<Integer,List<StringBuilder>>();
        int maxLen=getMaxLength(wordDict);
        boolean judge[]=new boolean [s.length()+1];
        judge[0]=true;
        List<StringBuilder> list=new ArrayList<StringBuilder>();
        list.add(new StringBuilder());
        map.put(0,list);
        for(int i=1;i<s.length()+1;++i) {
        	for(int j = 1; j <= maxLen && j <= i; j++) {//j为到i的距离
        		String nowString=s.substring(i-j, i);
        		if(judge[i-j]&&wordDict.contains(nowString)) {
        			judge[i]=true;
        			List<StringBuilder> nowList=map.get(i-j);
        			for(int k=0;k<nowList.size();++k) {
        				StringBuilder sb=nowList.get(k);
        				StringBuilder nsb=new StringBuilder(sb);
        				if(i-j!=0) {
        					nsb.append(" ").append(nowString);
        				}
        				else
        					nsb.append(nowString);
        				List<StringBuilder> newList=map.get(i);
        				if(newList!=null) {
        					newList.add(nsb);
        				}
        				else {
	        				newList=new ArrayList<StringBuilder>();
	        				newList.add(nsb);
	        				map.put(i,newList);
        				}
        			}
        		}
        	}
        }
        List<StringBuilder> resList=map.get(s.length());
        if(resList!=null&&resList.size()>0)
        	for(StringBuilder sb:resList)
        		this.res.add(sb.toString());
        return this.res;
    }
	
	private int getMaxLength(List<String> wordDict) {
		int res=0;
		for(int i=0;i<wordDict.size();++i) {
			res=Math.max(wordDict.get(i).length(), res);
		}
		return res;
	}
	
	
	/**
	 * describe:AC 99%的方法  用dfs min和max剪枝
 	 * 2018年6月4日 下午2:13:35
	 */
	public List<String> wordBreak2(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<String>();
        for(String word:wordDict){
            set.add(word);
            int curLen = word.length();
            min = (curLen<min)? curLen:min;
            max = (curLen>max)? curLen:max;
        }
        List<String> result = new ArrayList<String>();
        boolean[] invalid  = new boolean[s.length()];//invalid[i]: [i:] is unbreakable
        seperate(s,result, new StringBuilder(), 0, set, invalid);
        return result;
    }
	
	 public boolean seperate(String s,List<String> res, StringBuilder tmp, int index,HashSet<String> set, boolean[] invalid){
	        if(index == s.length()){
	            res.add(tmp.toString().trim());
	            return true;
	        }
	        boolean breakable = false;
	        int prelen = tmp.length();
	        
	        int rightbound = Math.min(s.length(),index+max);
	        for(int end = index+1; end<=rightbound; end++){
	            int curLen = end-index;
	            // if(curLen < min || curLen > max){
	            //     continue;
	            // }
	            //end==s.length()
	            if(end<s.length()&&invalid[end]){
	                continue;
	            }
	            String cur = s.substring(index, end);
	            if(set.contains(cur)){

	                tmp.append(" ").append(cur);
	                breakable |= seperate(s,res,tmp,end,set, invalid);
	                tmp.setLength(prelen);
	            }
	        }
	        invalid[index] = !breakable;
	        return breakable;
	    }

}
